package middle;

public class Solution_397 {

    public static void main(String[] args) {
        Solution_397 model = new Solution_397();
        System.out.println(model.integerReplacement(8));
        System.out.println(model.integerReplacement(7));
        System.out.println(model.integerReplacement(4));
        System.out.println(model.integerReplacement(Integer.MAX_VALUE));
        System.out.println(Integer.MAX_VALUE);
    }

    public int integerReplacement(int n) {
        if (n == 1) {
            return 0;
        } else if (n % 2 == 0) {
            return integerReplacement(n >> 1) + 1;
        } else {
            if (n == Integer.MAX_VALUE) {
                return integerReplacement((n - 1) >> 1) + 1;
            }
            return Math.min(integerReplacement((n + 1) >> 1), integerReplacement(n >> 1)) + 2;
        }
    }
}
